\subsection{Definition}
A random process, also known as a stochastic process, is a sequence of random variables \(X_n\) for \(n \in \mathbb N\).
A random walk is a random process that can be expressed as
\[
	X_n = x + Y_1 + \dots + Y_n
\]
where the \(Y_i\) are independent and identically distributed, and \(x\) is a deterministic number.
We will focus on the simple random walk on \(\mathbb Z\), which is defined by taking
\[
	\prob{Y_i = 1} = p;\quad \prob{Y_i = -1} = 1-p = q
\]
This can be thought of as a specific case of a Markov chain; it has the property that the path to \(X_i\) does not matter, all that matters is the value that we are at, at any point in time.

\subsection{Gambler's ruin estimate}
What is the probability that \(X_n\) reaches some value \(a\) before it falls to 0?
We will write \(\mathbb P_x\) for the probability measure \(\mathbb P\) with the condition that \(X_0 = x\), i.e.
\[
	\psub{x}{A} = \prob{A \mid X_0 = x}
\]
We define \(h(x) = \psub{x}{(X_n) \text{ hits } a \text{ before hitting 0}}\).
We can define a recurrence relation.
By the law of total probability, we have, for \(0 < x < a\),
\begin{align*}
	h(x) & = \psubx{(X_n) \text{ hits \(a\) before hitting 0} \mid Y_1 = 1} \cdot \psubx{Y_1 = 1}   \\
	     & + \psubx{(X_n) \text{ hits \(a\) before hitting 0} \mid Y_1 = -1} \cdot \psubx{Y_1 = -1} \\
	     & = p \cdot h(x+1) + q \cdot h(x-1)
\end{align*}
Note that
\[
	h(0) = 0;\quad h(a) = 1
\]
There are two cases; \(p=q = \frac{1}{2}\) and \(p \neq q\).
If \(p=q=\frac{1}{2}\), then
\[
	h(x) - h(x+1) = h(x-1) - h(x)
\]
We can then solve this to find
\[
	h(x) = \frac{x}{a}
\]
If \(p \neq q\), then
\[
	h(x) = ph(x+1) + qh(x-1)
\]
We can try a solution of the form \(\lambda^x\).
Substituting gives
\[
	p\lambda^2 - \lambda + q = 0 \implies \lambda = 1, \frac{q}{p}
\]
The general solution can be found by using the boundary conditions.
\[
	h(x) = A + B \left( \frac{q}{p} \right)^x \implies h(x) = \frac{\left( \frac{q}{p} \right)^x - 1}{\left( \frac{q}{p} \right)^a - 1}
\]
This is known as the `gambler's ruin' estimate, since it determines whether a gambler will reach a target before going bankrupt.

\subsection{Expected time to absorption}
Let us define \(T\) to be the first time that \(x = 0\) or \(x = a\).
Then \(T = \min \{ n \geq 0 \colon X_n \in \{ 0, a \} \}\).
We want to find \(\esubx{T} = \tau_x\).
We can apply a condition on the first step, and use the law of total expectation to give
\[
	\tau_x = p \esubx{T \mid Y_1 = 1} + q \esubx{T \mid Y_1 = -1}
\]
Hence
\[
	\tau_x = p (\tau_{x + 1} + 1) + q (\tau_{x - 1} + 1)
\]
We can deduce that, for \(0 < x < a\),
\[
	\tau_x = 1 + p \tau_{x+1} + q \tau_{x-1}
\]
and \(\tau_0 = \tau_a = 0\).
If \(p = q = \frac{1}{2}\), then we can try a solution of the form \(Ax^2\).
\[
	Ax^2 = 1 + \frac{1}{2}A(x+1)^2 + \frac{1}{2}A(x-1)^2
\]
This gives a general solution of the form
\[
	A = -1 \implies \tau_x = -x^2 + Bx + C \implies \tau_x = x(a-x)
\]
If \(p \neq q\), then we will try a solution of the form \(Cx\), giving
\[
	C = \frac{1}{q-p}
\]
The general solution has the form
\[
	\tau_x = \frac{x}{q-p} + A + B\left( \frac{q}{p} \right)^x \implies \tau_x = \frac{x}{q-p} - \frac{q}{q-p} \cdot \frac{\left( \frac{q}{p} \right)^x - 1}{\left( \frac{q}{p} \right)^a - 1}
\]
